#============================================================
# Create Time:			2020-11-04 12:47:14
# Last modify:			2020-11-16 12:08:01
# Writer:				Wenhao	1795902848@qq.com
# File Name:			IdiomsSolitaire.py
# File Type:			PY Source File
# Tool:					Windows -- vim & python
# Information:			
#============================================================

import pypinyin

class Node():
    def __init__(this):
        this.weight = 123456
        this.idioms = []

class IdiomsSolitaire():
    def __init__(this):
        with open('idioms.txt', 'r', encoding='utf-8') as f:
            lines = f.readlines()
        this.all_idioms = [line.strip() for line in lines]

        this.first_chars = [idiom[0] for idiom in this.all_idioms]
        this.last_chars = [idiom[-1] for idiom in this.all_idioms]

        this.first_char_pinyins = pypinyin.lazy_pinyin(this.first_chars)
        this.last_char_pinyins = pypinyin.lazy_pinyin(this.last_chars)

        this.pinyins = list(set(this.first_char_pinyins + this.last_char_pinyins))
        this.GRAPH_WIDTH = len(this.pinyins)
        this.visited = [False for i in range(this.GRAPH_WIDTH)]
        this.parent = [-1 for i in range(this.GRAPH_WIDTH)]
        return None

    def init_graph(this):
        graph = [ [Node() for j in range(this.GRAPH_WIDTH)] for i in range(this.GRAPH_WIDTH) ]
        for i, chars in enumerate(zip(this.first_char_pinyins, this.last_char_pinyins)):
            first_char, last_char = chars
            graph[this.pinyins.index(last_char)][this.pinyins.index(first_char)].idioms.append(i)

        for row, r_pinyin in enumerate(this.pinyins):
            for col, c_pinyin in enumerate(this.pinyins):
                if(graph[row][col].idioms):
                    weight = len(set(r_pinyin + c_pinyin))
                    graph[row][col].weight = weight

        for row in range(this.GRAPH_WIDTH):
            graph[row][row].weight = 0

        this.graph = graph
        return None

    def get_neibors(this, idx):
        return [ i for i, _ in enumerate(this.graph[idx])
                    if _.idioms
                    and not this.visited[i] ]

    def djkstra(this):
        stt_idx = this.pinyins.index('yi')
        buf = [stt_idx]
        this.visited[stt_idx] = True
        while(buf):
            weights = [(this.graph[stt_idx][node_idx].weight, node_idx) for node_idx in buf]
            min_weight = min(weights, key=lambda x:x[0])
            min_weight_idx = weights.index(min_weight)
            min_node_idx = weights[min_weight_idx][1]
            buf.remove(min_node_idx)

            neibors = this.get_neibors(min_node_idx)
            for neibor in neibors:
                buf.append(neibor)
                this.graph[min_node_idx][neibor].weight = min(
                        this.graph[stt_idx][neibor].weight,
                        this.graph[min_node_idx][neibor].weight + this.graph[stt_idx][min_node_idx].weight)
                this.visited[neibor] = True
                this.parent[neibor] = min_node_idx
        return None

    def bfs(this):
        stt_idx = this.pinyins.index('yi')
        buf = [stt_idx]
        this.visited[stt_idx] = True
        while(buf):
            pinyin_idx = buf.pop(0)
            neibors = this.get_neibors(pinyin_idx)
            for neibor in neibors:
                buf.append(neibor)
                this.visited[neibor] = True
                this.parent[neibor] = pinyin_idx
        return None

    def trace_back(this, pinyin):
        idx = this.pinyins.index(pinyin)
        parent_idx = this.parent[idx]
        while(parent_idx != -1):
            print(this.pinyins[idx], end='\t')
            for _ in this.graph[parent_idx][idx].idioms:
                print(this.all_idioms[_], end='\t')
            print()
            idx = parent_idx
            parent_idx = this.parent[idx]
        print('yi\t一个顶俩')
        return None

if __name__ == '__main__':
    machine = IdiomsSolitaire()
    machine.init_graph()
    #machine.bfs()
    machine.djkstra()
    while(True):
        pinyin = input('请输入成语第一个字的拼音：')
        machine.trace_back(pinyin)
        print()
